from XSY.Graph.Graph import *

class CheckerDAG:
    def __init__(self, G, V, e_filter=None):
        ''' ''' 
        self.cnt=0  # count pre, int
        self.cntP=0 # count post, int
        self.G = G # reference the graph checked
        self.V = V # scope of vertex under G
        self.pre = dict() # vertex to order index 
        self.post= dict() # vertex to order index
        self.bCycleDetected=False # flag indicating if cycle is detected or not

        for v in V:
            if v not in self.pre.keys():
                self.dfsR(v, e_filter)

    def dfsR(self, node, e_filter) :
        '''recursive depth-first search '''
        self.cnt += 1  # increase cnt by one
        self.pre[node] = self.cnt # assign pre index of node
        for v in self.G.outV(node, e_filter).intersection(self.V):
            if v not in self.pre.keys(): 
                self.dfsR(v, e_filter) # depth-frst search by recursive call 
            elif v not in self.post.keys(): # cyclic case
                self.bCycleDetected = True

        self.cntP += 1 # increase cntP by one
        self.post[node] = self.cntP # assign post index of node
        
    def isDAG(self): 
        '''if not cyclic is found, then G is DAG'''
        return not self.bCycleDetected; 

if __name__ == '__main__':
    g = Graph()
    g.addVtx(1); g.addVtx(2); g.addVtx(3)
    g.addEdge(1,2); g.addEdge(2,3)
    print "Is g a DAG?>", CheckerDAG(g, g.getVtxs()).isDAG()
    g.addEdge(3,1)
    print "Is g a DAG?>", CheckerDAG(g, g.getVtxs()).isDAG()

